#leetcode题目52：n皇后2
#难度：困难
#时间复杂度：O(n!)
#空间复杂度：O(n)
#方法：回溯

class Solution:
    def totalNQueens(self, n: int) -> int:
        col=[0]*n
        ans=[]
        on_path=[False]*n
        dia1=[False]*(2*n-1)
        dia2=[False]*(2*n-1)
        def dfs(r):
            for c in range(n):
                if r==n:
                    ans.append(["."*c+"Q"+"."*(n-c-1) for c in col])
                    return
                if not on_path[c] and not dia1[r+c] and not dia2[r-c]:
                    on_path[c]=dia1[r+c]=dia2[r-c]=True
                    col[r]=c
                    dfs(r+1)
                    on_path[c]=dia1[r+c]=dia2[r-c]=False


        dfs(0)
        return len(ans)


#测试数据
n=4
#预期输出：2
solution=Solution()
print(solution.totalNQueens(n))

n=1
#预期输出：1
solution=Solution()
print(solution.totalNQueens(n))

n=8
#预期输出：92
solution=Solution()
print(solution.totalNQueens(n)) 